Factor combinations

Time: O(NLogN); Space: O(LogN); medium

Numbers can be regarded as product of its factors.

For example,

8 = 2 x 2 x 2; = 2 x 4.

Write a function that takes an integer n and return all possible combinations of its factors.

Notes:

  • You may assume that n is always positive.

  • Factors should be greater than 1 and less than n.

Example 1:

Input: 12

Output:

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

Explanation:

  • 2 * 6 = 12

  • 2 * 2 * 3 = 12

  • 3 * 4 = 12

Example 2:

Input: 32

Output:

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Explanation:

  • 2 * 16 = 32

  • 2 * 2 * 8 = 32

  • 2 * 2 * 2 * 4 = 32

  • 2 * 2 * 2 * 2 * 2 = 32

  • 2 * 4 * 4 = 32

  • 4 * 8 = 32

[1]:

class Solution1(object):
    """
    Time: O(NLogN)
    Space: O(LogN)
    """
    def getFactors(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        result = []
        factors = []
        self.getResult(n, result, factors)
        return result

    def getResult(self, n, result, factors):
        i = 2 if not factors else factors[-1]
        while i <= n // i:
            if n % i == 0:
                factors.append(i)
                factors.append(n // i)
                result.append(list(factors))
                factors.pop()
                self.getResult(n // i, result, factors)
                factors.pop()
            i += 1

[2]:

s = Solution1()

n = 12
assert s.getFactors(n) == [
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

n = 32
assert s.getFactors(n) == [
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]